Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Minimize Maximum of Array

Problem Statement

Given a positive integer array nums, return the minimum possible value of the maximum integer of nums after performing multiple operations.

In one operation, you must:

  • Select any index i such that 1 <= i < n and nums[i] > 0.
  • Increase nums[i - 1] by 1.
  • Decrease nums[i] by 1.

Examples

Example 1:

  • Input: nums = [4, 5, 3, 2, 1, 6]
  • Expected Output: 5
  • Justification: We can perform operations to decrease the last element (6) to 5 and increase the fifth element to 2. Here, the maximum array element is 5.

Example 2:

  • Input: nums = [1, 2, 3, 4]
  • Expected Output: 3
  • Justification: We can decrease the last element (4) to 3 and increase the third element to 4, then decrease the third element (now 4) to 3, increasing the second element to 3. The array becomes [1, 3, 3, 3], with the maximum being 3.

Example 3:

  • Input: nums = [8, 2, 2, 3]
  • Expected Output: 8
  • Justification: We can't perform any operation to minimize the maximum value of the array. So, 8 is the minimum possible value of the maximum integer.

Solution

To solve this problem, we adopt a strategy that leverages the cumulative sum of the array elements to find the minimum possible maximum value after performing the allowed operations. The core idea is to iteratively calculate the cumulative sum up to each index and use this sum to determine the maximum average value that can be achieved by redistributing the numbers.

This approach is grounded in the insight that the minimum possible maximum value, after any number of operations, is essentially the ceiling of the maximum average of the cumulative sums up to each point in the array. By calculating these averages and keeping track of the highest one, we can deduce the minimum maximum value achievable. This method is effective because it directly addresses the problem's goal without needing to explicitly perform the redistributions, thereby offering a more efficient solution.

Step-by-Step Algorithm

  1. Initialize a variable sum to 0 to keep track of the cumulative sum of the array elements.
  2. Initialize another variable ans to 0 to store the maximum average found during the iteration.
  3. Iterate through the array using a loop:
    • For each element at index i, add it to sum to update the cumulative sum.
    • Calculate the average up to the current index as (sum + i) / (i + 1). This formula accounts for the zero-based indexing and ensures that the division is done considering the total number of elements counted so far.
    • Update ans with the maximum value between the current ans and the calculated average. This step ensures that ans always holds the highest average value found.
  4. After completing the iteration, ans will hold the minimum possible maximum value of the array after the operations. Convert ans to an integer (if necessary) and return it as the solution.

Algorithm Walkthrough

Input: nums = [4, 5, 3, 2, 1, 6].

  • Initial State:

    • nums = [4, 5, 3, 2, 1, 6]
    • sum = 0
    • ans = 0
  • Iteration 1:

    • i = 0, nums[i] = 4
    • sum = 4
    • average = (4 + 0) / (0 + 1) = 4
    • ans = max(0, 4) = 4
  • Iteration 2:

    • i = 1, nums[i] = 5
    • sum = 4 + 5 = 9
    • average = (9 + 1) / (1 + 1) = 5
    • ans = max(4, 5) = 5
  • Iteration 3:

    • i = 2, nums[i] = 3
    • sum = 9 + 3 = 12
    • average = (12 + 2) / (2 + 1) = 4.666...
    • ans = max(5, 4.666...) = 5
  • Iteration 4:

    • i = 3, nums[i] = 2
    • sum = 12 + 2 = 14
    • average = (14 + 3) / (3 + 1) = 4.25
    • ans = max(5, 4.25) = 5
  • Iteration 5:

    • i = 4, nums[i] = 1
    • sum = 14 + 1 = 15
    • average = (15 + 4) / (4 + 1) = 3.8
    • ans = max(5, 3.8) = 5
  • Iteration 6:

    • i = 5, nums[i] = 6
    • sum = 15 + 6 = 21
    • average = (21 + 5) / (5 + 1) = 4.333...
    • ans = max(5, 4.333...) = 5
  • Final State:

    • ans = 5

Code

Java

. . . .

Complexity Analysis

  • Time Complexity: The algorithm iterates through the array once. Therefore, the time complexity is , where n is the length of the array.
  • Space Complexity: The algorithm operates in-place, requiring no additional space proportional to the input size. Thus, the space complexity is , as only a constant amount of extra space is used.
Minimize Maximum of Array (medium)
Asteroid Collision (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis